package com.xmh.leetcode.other.leetCode;

import org.junit.Test;

import java.util.Arrays;

/**
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 * <p>
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 * <p>
 * 问总共有多少条不同的路径？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/unique-paths
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class DifferentPaths {

    @Test
    public void uniquePaths() {
//        for (int i = 1; i <= 15; i++) {
//            int k = getPath(i, i);
//            System.out.println(k);
//        }
//        Arrays.fill(new int[]{1}, 1);

        System.out.println(getPath(4, 4));
    }


    /**
     * 方法递归
     *
     * @param row
     * @param line
     * @return
     */
    private int getPath(int row, int line) {
        return right(1, 1, row, line);
    }

    private int right(int row, int line, int s_row, int s_line) {
        if (row == s_row && line == s_line) {
            return 1;
        }
        int i = 0;

        if (row != s_row) {
            i += right(row + 1, line, s_row, s_line);
        }
        if (line != s_line) {
            i += right(row, line + 1, s_row, s_line);
        }
        return i;
    }

    /**
     * 动态规划 1 空间复杂度 O(2n)
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[] pre = new int[n];
        int[] cur = new int[n];
        Arrays.fill(pre, 1);
        Arrays.fill(cur, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] = cur[j - 1] + pre[j];
            }
            pre = cur.clone();
        }
        return pre[n - 1];
    }

    /**
     * 动态规划 2 空间复杂度 O(n)
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths2(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] += cur[j - 1];
            }
        }
        return cur[n - 1];
    }


    public int uniquePaths_1(int m, int n) {
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            grid[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            grid[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
            }
        }
        return grid[m - 1][n - 1];
    }

    /**
     * 因为在这里面每个点的路径都是这个点的 上一个点的路径数 + 左边点的路径数 ，因此只要将上一行和本行的数值记录下来就能推导目标点的
     * 路径数，可以将空间复杂度由 O(m * n) 优化为 O(2n)
     *
     * @param m -
     * @param n -
     * @return -
     */
    public int uniquePaths_2(int m, int n) {
        int[] preLine = new int[n];
        int[] curLine = new int[n];
        Arrays.fill(preLine, 1);
        Arrays.fill(preLine, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                curLine[j] = preLine[j] + curLine[j - 1];
            }
            preLine = curLine.clone();
        }
        return curLine[n - 1];
    }

    /**
     * 从解法二可以看出，我们求一个点需要的是它头上的那个点和它本行左边的那个点，只要有这两个点，那么就能够计算出当前点
     * 所以可以直接将两行数据优化为一行，每次循环都会提前计算它左边的点，这个左边的点就可以理解成本行左边的那个点，而因为
     * 当前点还未进行计算，这个位置上实际存储的数据是它头上的那个点（上一行）的数据，因此空间复杂度优化为O(n)
     *
     * @param m -
     * @param n -
     * @return -
     */
    public int uniquePaths_3(int m, int n) {
        int[] arr = new int[n];
        Arrays.fill(arr, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                arr[j] += arr[j - 1];
            }
        }
        return arr[n - 1];
    }

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }

        if (nums[nums.length - 1] + nums[nums.length - 2] == target) {
            return new int[]{nums.length - 1, nums.length - 2};
        }

        return null;
    }

    @Test
    public void testsuze() {
        int[] x = twoSum(new int[]{2,7,11,15}, 9);
        for (int i : x) {
            System.out.println(i);
        }

    }

}
